/*
 * Author: 杭嘉雯 1300012862
 * 
 * Outline:
 * 通过双向广搜计算回复超过x条的相互认识的人之间的最短距离。
 * 复杂度O(num_query * (num_person + num_relation))。
 * 
 * Optimization:
 * 使用C++11的特性，用unordered_set和unordered_map来
 * 替换set和map，以获得更高的效率。
 *
 * Performance:
 * 1k的数据大概需要4s。
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

unordered_map<int,int> personID,commentID;              // 离散化人和评论编号
unordered_map<int,int> comment_person;                  // 将评论编号与所发之人的编号对应
unordered_map<int,unordered_set<int>> person_person;    // 存储每一个人认识的所有人的编号
map<pair<int,int>,int> pair_comment;                    // 存储互相认识的人之间的评论回复数

string data_path;
int data_size;
string query_file;
string answer_file;

int cnt_person=0, cnt_comment=0;
char buf[MAXN];

int* now;
bool* flag;
int sign;
int* dist;
int* dqueue;

/* 将每个人的编号读入，用unordered_map进行离散化处理 */
void handle_Person()
{
    string person_data_file = data_path + "person.csv";
    FILE *f_person = fopen(person_data_file.c_str(), "r");

    fgets(buf, 1000, f_person);
	while(fgets(buf, 1000, f_person) != NULL)
	{
		int i = 0;
		string tmp;
		while(1)
		{
			if(buf[i] == '|') { i++; break;}
			tmp += buf[i];
			i++;
		}
		personID[atoi(tmp.c_str())] = ++cnt_person;
	}
    fclose(f_person);
}

/* 将每一条评论的编号读入，用unordered_map进行离散化处理 */
void handle_Comment()
{
    string comment_data_file = data_path + "comment.csv";
    FILE *f_comment = fopen(comment_data_file.c_str(), "r");

     fgets(buf, 1000, f_comment);
	while(fgets(buf, 1000, f_comment) != NULL)
	{
		int i = 0;
		string tmp;
		while(1)
		{
			if(buf[i] == '|') { i++; break;}
			tmp += buf[i];
			i++;
		}
		commentID[atoi(tmp.c_str())] = ++cnt_comment;
	}
    fclose(f_comment);
}

/* 将评论与其发布者对应编号用unordered_map存储 */
void handle_Comment_hasCreator_person()
{
	string comment_hasCreator_person_data_file = data_path + "comment_hasCreator_person.csv";
    FILE *f_comment_hasCreator_person = fopen(comment_hasCreator_person_data_file.c_str(), "r");

	int c, p,comment,person;
	fgets(buf, 1000, f_comment_hasCreator_person);
	while(fscanf(f_comment_hasCreator_person, "%d|%d", &c, &p) != EOF)
	{
		comment=commentID[c];
		person=personID[p];
		comment_person[comment]=person;
	}
	fclose(f_comment_hasCreator_person);
}

/* 处理人与人之间认识的数据，用unordered_set存储每一个人认识的所有人的编号 */
void handle_PersonKnowsPerson()
{
    string person_knows_person_data_file = data_path + "person_knows_person.csv";
    FILE *f_person_knows_person = fopen(person_knows_person_data_file.c_str(), "r");

    int tmp1, tmp2, person1, person2;
	fgets(buf, 1000, f_person_knows_person);
	while(fscanf(f_person_knows_person, "%d|%d", &tmp1, &tmp2) != EOF)
	{
		person1=personID[tmp1];
		person2=personID[tmp2];
		person_person[person1].insert(person2);
		pair_comment[make_pair(person1,person2)]=0;
	}
    fclose(f_person_knows_person);
}

/* 读入评论与回复的数据，计算出两个互相认识的人之间的互相回复数 */
void handle_Comment_replyOf_comment()
{
	string comment_replyOf_comment_data_file = data_path + "comment_replyOf_comment.csv";
	FILE *f_comment_replyOf_comment = fopen(comment_replyOf_comment_data_file.c_str(), "r");

	int tmp1, tmp2,person1,person2;
	fgets(buf, 1000, f_comment_replyOf_comment);
	while(fscanf(f_comment_replyOf_comment, "%d|%d", &tmp1, &tmp2) != EOF)
	{
		person1=comment_person[commentID[tmp1]];
		person2=comment_person[commentID[tmp2]];
		if(person_person.find(person1)!=person_person.end())
		{
			if(person_person[person1].find(person2)!=person_person[person1].end())
			{
				pair<int,int> tmp=make_pair(person1,person2);
				if(pair_comment.find(tmp)!=pair_comment.end())
					++pair_comment[tmp];
			}
		}
	}
	unordered_map<int,unordered_set<int>>::iterator p;
	unordered_set<int>::iterator q;
	for(p=person_person.begin();p!=person_person.end();++p)
	{
		for(q=p->second.begin();q!=p->second.end();++q)
		{
			pair<int,int>tmp1=make_pair(p->first,*q);
			pair<int,int>tmp2=make_pair(*q,p->first);
			pair_comment[tmp1]=pair_comment[tmp2]=min(pair_comment[tmp1],pair_comment[tmp2]);
		}
	}
	
	fclose(f_comment_replyOf_comment);
}

/* 利用双向广搜寻求两个互相认识且回复数超过x条的人之间的最小路径 */
int result(int person1,int person2,int x)
{
	if(person1==person2) return 0;
	++sign;
	int p1=personID[person1];
	int p2=personID[person2];
	dist[p1]=dist[p2]=0;
	now[p1]=now[p2]=sign;
	flag[p1]=0;
	flag[p2]=1;
	dqueue[0]=p1;
	dqueue[1]=p2;
	int l=0,r=2;
	while(l<r)
	{
		int p=dqueue[l];
		unordered_set<int>::iterator q;
		for(q=person_person[p].begin();q!=person_person[p].end();++q)
		{
			pair<int,int>tmp=make_pair(p,*q);
			if(pair_comment[tmp]>x)
			{
				if(now[*q]==sign&&(flag[p]^flag[*q]))
					return dist[p]+dist[*q]+1;
				else
				{
					if(now[*q]!=sign)
					{
						dist[*q]=dist[p]+1;
						flag[*q]=flag[p];
						now[*q]=sign;
						dqueue[r++]=*q;
					}
				}
			}
		}
		++l;
	}
	return -1;
}

/* 初始化，读入测试数据，输出答案 */
void handle_query1()
{
	FILE *f_query = fopen(query_file.c_str(), "r");
    FILE *f_answer = fopen(answer_file.c_str(), "w");

	dist = new int[cnt_person];
	dqueue = new int[cnt_person];
	now = new int[cnt_person];
	flag = new bool[cnt_person];

    int p1, p2, x;
    while (fscanf(f_query, "%d%d%d", &p1, &p2, &x) != EOF) 
        fprintf(f_answer, "%d\n",result(p1,p2,x));

	delete[] dist;
	delete[] dqueue;
	delete[] now;
	delete[] flag;

    fclose(f_query);
    fclose(f_answer);
}

/* 主函数 */
int main(int argc, char *argv[]) 
{
#ifndef LOCAL
    data_path = argv[1];
    data_size = atoi(argv[2]);
    query_file = argv[3];
    answer_file = argv[4];
#else
	data_path = string("../../../data/1k-network/");
    data_size = atoi("1000");
    query_file = string("../query1.in");
    answer_file = string("../query1.out");
#endif

	handle_Person();
	handle_Comment();
	handle_Comment_hasCreator_person();
    handle_PersonKnowsPerson();
	handle_Comment_replyOf_comment();
	handle_query1();

    return 0;
}
